package com.Z行层序遍历二叉树;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
 class Solution1 {
	List<List<Integer>> result = new ArrayList<List<Integer>>();
    public List<List<Integer>> levelOrder(TreeNode root) {
    	 List<Integer> list = new ArrayList<Integer>();
    	 Queue<TreeNode> q = new LinkedList<TreeNode>();
         TreeNode last,nlast = null;
         //nlast是指向每一行的最后一个点，last指向当前的这个点
         last=root;
         q.offer(root);
         TreeNode temp;
         int count=1;//计数层数
         while(!q.isEmpty()) {
        	 temp=q.poll();
        	 if(count%2!=0) {
        		 list.add(temp.val);//奇数层
        	 }else {
        		 list.add(0, temp.val);//偶数层
        	 }
        	 
        	 if(temp.left!=null) {
        		 q.offer(temp.left);
        		 nlast=temp.left;
        	 }
        	 if(temp.right!=null) {
        		 q.offer(temp.right);
        		 nlast=temp.right;
        	 }
        	 if(temp==last) {//一行结束
        		 last=nlast;
        		 result.add(list);
        		 list = new ArrayList<Integer>();
        		 count++;
        	 }
         }
		 return result;
        
    }
}
public class Solution {
	
    public TreeNode buildTree(int[] preorder, int[] inorder) {
    	if(preorder.length<1||inorder.length<1) {
    		TreeNode root=null;
    		return root;
    	}
    	if(preorder.length==1&&inorder.length==1) {
    		TreeNode root=new TreeNode(preorder[0]);
    		return root;
    	}
        int rootval=preorder[0];
        TreeNode root=new TreeNode(rootval);
        int []info=leflen_root_rightlen(inorder,rootval);
        int rindex=info[1];
        int left=info[0];
        int right=info[2];
        int [] preleft=new int[left];
        int [] preright=new int[right];
        int [] inleft=new int[left];
        int [] inright=new int[right];
        System.arraycopy(preorder, 1, preleft, 0, left);
        System.arraycopy(preorder, 1+left, preright, 0, right);
        System.arraycopy(inorder, 0, inleft, 0, left);
        System.arraycopy(inorder, rindex+1, inright, 0, right);
        root.left=buildTree(preleft,inleft);
        root.right=buildTree(preright,inright);
        return root;
        
    }
//    public TreeNode BulidTreeCore(int [] preorder,int prestart,int preend,int[] inorder,int instart,int end){
//        return null;
//    }
    public int[] leflen_root_rightlen(int[] inorder,int n){
        int indexroot=0;
        for(int i=0;i<inorder.length;i++){
            if(inorder[i]==n){
                indexroot=i;
                break;
            }
        }
        int[] temp=new int[3];
        temp[0]=indexroot;//左子树长度
        temp[1]=indexroot;//根节点下标
        temp[2]=inorder.length-1-indexroot;//右子树长度
        return temp;
    }
}
